package 左哥算法.ch07图;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

public class Ch02最小生成树 {

    @Test
    public void test01(){
        Integer[][] arr={
                {1,0,1,1,0,0,0},
                {2,0,0,1,0,0,1},
                {3,0,0,0,1,0,0},
                {4,0,0,0,0,0,0},
                {5,0,1,0,1,0,0},
                {6,0,0,0,1,0,0},
        };
        Graph graph = new Graph(arr);
        topology(graph);
    }
    /**
     * 图的拓扑排序：
     *      首先图中不能存在环
     *      先从图中入度为0的节点出发，然后擦除该节点与其的影响，再找下一个入度为0的节点，直到整个图遍历完成
     *      注：一个图可能存在多个不同的拓扑排序
     * 队列+Map思路：
     *      1.准备一个Map，用于存放所有节点的入度，再准备一个队列，用于存放入度为0的节点
     *      2.遍历图中所有节点，将其的入度备份到一个单独的Map中，将图中入度为0的节点放入队列
     *      3.对队列节点出队，将该节点的邻居入度-1（擦除影响），将入度为0的子节点入队
     *      4.重复3
     */
    public void topology(Graph graph){
        Map<Node,Integer> inMap=new HashMap<>();
        Queue<Node> queue=new LinkedList<>();
        for (Node value : graph.nodes.values()) {
            inMap.put(value,value.in);
            if (value.in==0){
                queue.add(value);
            }
        }
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.val+" ");
            for (Node next : node.nexts) {
                Integer in = inMap.get(next);
                inMap.put(next,--in);
                if (in==0){
                    queue.add(next);
                }
            }
        }
    }

    @Test
    public void test(){
        Integer[][] arr={
                {1,0,7,2,100,0},
                {2,7,0,0,1000,1000_000},
                {3,2,0,0,4,0},
                {4,100,1000,4,0,0},
                {5,0,1000_000,0,0,0},
        };
        Graph graph = new Graph(arr);
        for (Edge edge : kruskalMST(graph)) {
            System.out.print(edge.from+"->"+edge.to+"="+edge.weight+"\t");
        }
        System.out.println();
        for (Edge edge : primMST(graph)) {
            System.out.print(edge.from+"->"+edge.to+"="+edge.weight+"\t");
        }
    }
    /**
     * ch02：最小生成树，一张无向图，你需要保证所有点都能连通，并且连通后边的权值是最小的
     *  并查集思路（k算法）：
     *      用一个map存放每个节点的父节点（上一个连接自己的节点），如果没有节点连接自己，父节点则为自己
     *      对所有的边进行排序，对每次最小一条边的两头节点进行集合查找操作（查看两个节点是否存在共同的父节点）
     *          如果不存在则表示该边的两个节点没有连通，将两个节点的父节点设为同一个（已经连通）
     *          如果存在则表示有更小的边使这两个点连通，不需要当前边
     *      直到将所有边都筛选完毕
     */
    public List<Edge> kruskalMST(Graph graph){
        List<Edge> edges = graph.edges.stream().sorted((o1, o2) -> o1.weight - o2.weight)
                .collect(Collectors.toList());  //组合
        List<Edge> res=new ArrayList<>();
        UnionFindSet<Node> mySet = new UnionFindSet(graph.nodes.values());
        for (Edge edge : edges) {
            if (!mySet.isSameSet(edge.from,edge.to)) {  //是否连通
                res.add(edge);
                mySet.union(edge.from,edge.to);
            }
        }
        return res;
    }

    /**
     *  ch02：最小生成树p算法
     *  p算法思路：
     *      准备一个存放点的set集合和存放解锁边的优先级队列
     *      从任意一个点出发，对该点的边进行解锁，
     *      队列弹出解锁的边中最小的一条，如果这条边的to点没有被加载，
     *      则将这条边的to点保存起来，并将to点附近的边解锁，如果被解锁，则再找下一条边
     *      重复上两个步骤
     */
    public List<Edge> primMST(Graph graph){
        Set<Node> nodes=new HashSet<>();
        Queue<Edge> edges=new PriorityQueue<>(((o1, o2) -> o1.weight-o2.weight));   //小根堆
        List<Edge> list=new ArrayList<>();      //走过的边
        Iterator<Node> iterator = graph.nodes.values().iterator();
        Node node=iterator.next();
        nodes.add(node);
        edges.addAll(node.edges);

        while (nodes.size()<graph.nodes.values().size()){   //所有点都加载完毕
            Edge edge = edges.poll();
            if (!nodes.contains(edge.to)){      //已经走过的点
                list.add(edge);
                nodes.add(edge.to);
                edges.addAll(edge.to.edges);
            }
        }
        return list;
    }

    @Test
    public void test03(){
        Integer[][] arr={
                {1,0,3,15,9,0},
                {2,3,0,2,0,200},
                {3,15,2,0,7,14},
                {4,9,0,7,0,16},
                {5,0,200,14,16,0},
        };
        Graph graph = new Graph(arr);
        Map<Node, Integer> map = dijkstraMST(graph);
        Map<Node, Integer> map2 = dijkstra2(graph);
        System.out.println();
    }

    /**
     * ch03最小生成树的变体：求每个节点到某个起点的最短距离。(可以通过记录每个节点的上一条边来实现最小生成树)
     *  Dijkstra最短距离算法思路：
     *      1.将每个节点放入一个hashMap中，k是该节点，v是起始节点到该节点的距离（默认为无穷大）
     *      2.准备一个hashSet用来表示已经走过的节点
     *      3.从Map中找到一个离起点最近的点，从该点走向它所有邻居，并设置他们到起点的距离(如果比原来距离要短)，将该点设为已经走过
     *      4.重复3直到所有点都已经走过
     */
    public Map<Node,Integer> dijkstraMST(Graph graph){
        Map<Node,Integer> map=new HashMap<>();
        Set<Node> selectedSet=new HashSet<>();
        for (Node value : graph.nodes.values()) {
            map.put(value,Integer.MAX_VALUE);    //所有节点初始距离起点为无穷大
        }
        Iterator<Node> iterator = graph.nodes.values().iterator();
        Node head = iterator.next();    //起点
        map.put(head,0);
        Node node = selectMin(map, selectedSet);
        while (node!=null){
            Integer distance = map.get(node);   //当前节点距起点的距离
            for (Edge edge : node.edges) {
                if (edge.weight+distance<map.get(edge.to)){     //如果新的路径比原来的路径要短
                    map.put(edge.to,edge.weight+distance);
                }
            }
            node = selectMin(map, selectedSet);
        }
        return map;
    }

    /**
     *  返回map中距离起点最近且未走过的节点
     */
    public Node selectMin(Map<Node,Integer> map,Set<Node> set){
        List<Map.Entry<Node, Integer>> sorted = map.entrySet().stream() //返回一个排好序的集合
                .sorted((o1, o2) -> o1.getValue() - o2.getValue()).collect(Collectors.toList());
        for (Map.Entry<Node, Integer> entry : sorted) {
            Node key = entry.getKey();
            if (!set.contains(key)){
                set.add(key);        //将节点设定为已走过
                return key;
            }
        }
        return null;
    }

    @Test
    public void test04(){
        Integer[][] arr={
                {1,0,5,20,17,0},
                {2,5,0,2,0,10},
                {3,20,2,0,1,0},
                {4,17,0,1,0,5},
                {5,0,10,0,10,0},
        };
        Graph graph = new Graph(arr);
        Map<Node, Integer> map = dijkstra2(graph);
        System.out.println(map);
    }

    /**
     * ch04dj特斯拉改写堆：求每个节点到某个起点的最短距离
     *      1.有一个堆，向堆中添加节点和它到起点的距离，会自动生成最近的节点，可以通过pop获取
     *      2.将头节点入堆
     *      3.从堆中返回一个最近的节点，将其所有邻居都添加或更新到堆中（以及邻居到起点的距离）
     *      4.重复3直到堆为空
     */
    public Map<Node,Integer> dijkstra2(Graph graph){
        NodeHeap nodeHeap=new NodeHeap(graph.nodes.size());
        Iterator<Node> iterator = graph.nodes.values().iterator();
        Node head = iterator.next();    //起点
        nodeHeap.addOrUpdateOrIgnore(head,0);

        while (nodeHeap.isNotEmpty()){
            NodeHeap.NodeRecord record = nodeHeap.pop();
            for (Edge edge : record.node.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to,record.distance+edge.weight);
            }
        }
        return nodeHeap.distanceMap;
    }
}

/**
 * 并查集
 */
class UnionFindSet<T>{
    Map<T,T> map;

    public UnionFindSet(Collection<T> collection) {
        map=new HashMap<>();
        for (T t : collection) {
            map.put(t,t);
        }
    }

    public void union(T o1, T o2){
        map.put(find(o2),find(o1));
    }

    public T find(T node){
        T father = map.get(node);
        //如果当前节点是祖先节点则返回
        if (father==node){
            return node;
        }
        //不是则继续查找
        father=find(father);
        map.put(node,father);
        return father;
    }

    //两个节点的祖先是否相同
    public boolean isSameSet(T o1,T o2){
        return find(o1)==find(o2);
    }
}

/**
 * dijkstra改写小顶堆
 * 每次返回距离起点最近的节点与它的距离，并将其删除
 */
class NodeHeap {
    Node[] nodes;
    Map<Node,Integer> indexMap;     //节点在堆中的位置
    Map<Node,Integer> distanceMap;     //节点距离起点的位置
    int heapSize;

    public NodeHeap(int size) {
        this.nodes=new Node[size];
        indexMap=new HashMap<>(size);
        distanceMap =new HashMap<>(size);
    }

    /**
     * 如果节点不存在则添加
     * 节点存在且比原来要近则更新，更远则不更新
     */
    public void addOrUpdateOrIgnore(Node node,int distance){
        if (distanceMap.containsKey(node)){
            if (distance<distanceMap.get(node)){
                heapInsert(node,indexMap.get(node),distance);
                heapify(indexMap.get(node));
            }
            return;
        }
        heapInsert(node,heapSize++,distance);
    }

    /**
     * 返回堆中距离起点最近的节点，并将其移出至堆外
     */
    public NodeRecord pop(){
        Node node=nodes[0];
        swap(0,--heapSize); //头节点换至最后，堆的容量减一，即不要最后的节点
        heapify(0);     //在0位置上重构堆
        return new NodeRecord(node,distanceMap.get(node));
    }

    public boolean isNotEmpty(){
        return heapSize>0;
    }

    /**
     * 插入一个节点，并为他设置距离，索引，以及入数组
     */
    public void heapInsert(Node node,int index,int distance){
        nodes[index]=node;
        indexMap.put(node,index);
        distanceMap.put(node,distance);

        Node parentNode=nodes[(index-1)/2];
        while (distanceMap.get(node)<distanceMap.get(parentNode)){    //和父亲对比，直到自己比父亲大，否则一直换下去
            swap(index,(index-1)/2);
            index=(index-1)/2;
            parentNode=nodes[index];
        }
    }

    /**
     * 从指定位置对堆进行向下重构
     */
    public void heapify(int index){
        int left=index*2+1;
        while (left<heapSize){
            int minIndex = left+1<heapSize&&distanceMap.get(nodes[left+1]) < distanceMap.get(nodes[left]) ?
                    left+1: left;
            if (distanceMap.get(nodes[index])<distanceMap.get(nodes[minIndex])) {   //当前节点仍是最近节点
                return;
            }
            swap(minIndex,index);
            index=minIndex;
            left=index*2+1;
        }
    }

    public void swap(int a,int b){
        Node node=nodes[a];
        nodes[a]=nodes[b];
        nodes[b]=node;
        indexMap.put(nodes[a],a);
        indexMap.put(nodes[b],b);
    }

    static class NodeRecord{
        Node node;
        int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }
}
